# 105. 油漆面积(好题, 线段树)
# https://www.lanqiao.cn/problems/105/learning/?page=1&first_category_id=1&second_category_id=3
# Date:2025/2/6

"""线段树
线段树主要用于处理区间查询和区间更新问题.
它将一个数组分解成多个区间, 并以树的形式组织这些区间, 使得在 O(logn) 的时间复杂度内完成查询和更新操作.

主要用途:
1. 区间和、区间最小值/最大值、区间乘积等查询
2. 区间更新（如区间加法、区间赋值）
3. 动态维护区间信息

使用条件:
问题满足区间可加性, 即父区间的答案可以由子区间合并得到.

线段树是一个完全二叉树, 每个节点表示数组的一个子区间. 
根节点: 表示整个数组的范围. 
叶子节点: 表示数组中的单个元素. 
父子关系: 每个非叶子节点的两个子节点分别表示父节点区间的左右两部分. 

假设有一个数组 [2,4,5,7,8,9]:
                        [0,5]
                     /         \
                [0,2]          [3,5]
               /     \         /     \
           [0,1]    [2,2]   [3,4]   [5,5]
          /    \            /    \
      [0,0]  [1,1]      [3,3]  [4,4]
根节点 [0,5] 表示整个数组的区间. 叶子节点如 [0,0] 表示数组中的单个元素 2. 
每个节点存储与其区间相关的信息（如区间和、最大值等）.

本体的求解思路:
https://www.cnblogs.com/GarrettWale/p/12493987.html
此外, 可以使用暴力法求解: 创建一个足够大的二维数组模拟矩阵, 给每个矩形都填充1，而其余的地方都填充0，这样最后统计1的小正方形个数。

此类问题一般都是用 线段树 + 扫描法 来计算；
可以想象成一根假想的线，将图从左往右或从右往左或自下而上或自上而下"扫描"一遍，至于扫描的是什么则根据具体应用选择。
扫描线可以计算矩形面积、周长，可以计算线段交点，可以实现多边形扫描转换，在图的处理方面经常用到。

我们将使用一个图片来说明:
    |--------|
    |        |
    |      |-|------|
    |      | |      |
    |------|-|      |
           |        |
        |--|--------|----|
        |  |        |    |
        |  |--------|    |
        |                |
        |----------------|
添加扫描线:
   1 |---|--|-|
   0 |   |  | |
   9 | 1 | 2| |------|
   8 |   |  | |      |
   7 |---|--| |      |
   6        |3|      |
   5     |--| |   4  |----|
   4     |  | |      |    |
   3     | 2| |      |  5 |
   2     |  | |      |    |
   1     |--|-|------|----|
   0 1234567890123456789012
扫描线按x轴坐标从左到右扫描，动态维护当前被覆盖的y轴区间长度。
线段树则动态维护当前被覆盖的 y 轴区间总长度。在扫描每条竖直边时，使用线段树高效更新和查询 y 轴上的被覆盖区间。

具体到上面的图片来说, 可以看到通过扫描, 上图被划分为5个不同的区域
其中x轴上的数值被作为线段树中的节点, 对应y轴边长为存储的对象
"""


def paint_area(rectangles):
    """
    ChatGPT给出的答案
    计算所有矩形的并集面积
    :param rectangles: 每个矩形用 (x1, y1, x2, y2) 表示, 矩形边平行于坐标轴
    :return: 所有矩形覆盖区域的总面积
    """
    events = []  # 存储扫描线事件, 每个事件格式: (x, y1, y2, typ) typ为表示加入区间或离开区间的标记: 1为加入 -1为离开
    y_coords = set()  # 用于离散化的 y 坐标集合

    # 构造事件: 确保 (x1,y1) 为左下角, (x2,y2) 为右上角
    for (x1, y1, x2, y2) in rectangles:
        # 如果输入的坐标无序, 则先排序
        if x1 > x2:
            x1, x2 = x2, x1
        if y1 > y2:
            y1, y2 = y2, y1
        # 左边界事件, 表示在 x = x1 处加入区间 [y1,y2]
        events.append((x1, y1, y2, 1))
        # 右边界事件, 表示在 x = x2 处移除区间 [y1,y2]
        events.append((x2, y1, y2, -1))
        y_coords.add(y1)
        y_coords.add(y2)

    # 对事件按照 x 坐标排序（x 坐标相同时, 先处理加入事件, 再处理移除事件）
    # 也就是先比较第一个元素作升序排列, 如果第一个元素相同, 就比较第四个元素作降序排列
    events.sort(key=lambda e: (e[0], -e[3]))

    # 离散化 y 坐标
    ys = sorted(y_coords)
    # 建立 y 坐标到索引的映射（后续在线段树中使用）
    y_to_index = {y: i for i, y in enumerate(ys)}

    # 构造线段树所需的数据结构
    n = len(ys)
    seg_count = [0] * (4 * n)  # 记录该区间被覆盖的次数
    seg_length = [0] * (4 * n)  # 记录该节点所代表的 y 区间长度（若被覆盖, 则为实际区间长度, 否则为其子区间和）

    def update(node, start, end, l, r, val):
        """
        线段树区间更新
        :param node: 当前节点编号
        :param start: 当前节点表示的 y 坐标在离散化数组 ys 中的起始索引
        :param end: 当前节点表示的 y 坐标在离散化数组 ys 中的结束索引（不包含）
        :param l: 待更新区间在 ys 中的起始索引
        :param r: 待更新区间在 ys 中的结束索引（不包含）
        :param val: 增加的值（加入为 +1, 移除为 -1）
        """
        # 无交集情况
        if r <= start or end <= l:
            return
        # 当前区间完全被覆盖
        if l <= start and end <= r:
            seg_count[node] += val
        else:
            mid = (start + end) // 2
            update(node * 2, start, mid, l, r, val)
            update(node * 2 + 1, mid, end, l, r, val)
        # 更新当前节点的覆盖长度: 
        if seg_count[node] > 0:
            # 当前区间被至少一层覆盖, 则整个区间都算覆盖
            seg_length[node] = ys[end] - ys[start]
        else:
            # 当前区间未被完全覆盖, 则由子节点贡献
            if end - start == 1:
                seg_length[node] = 0
            else:
                seg_length[node] = seg_length[node * 2] + seg_length[node * 2 + 1]

    area = 0
    prev_x = events[0][0]  # 初始化上一个 x 坐标

    # 扫描所有事件
    for x, y1, y2, typ in events:
        dx = x - prev_x  # 当前 x 与上一个 x 的差值
        # 当前激活区间总长度 seg_length[1] 表示整个 y 轴的覆盖长度
        area += seg_length[1] * dx
        # 更新线段树, 更新区间 [y1, y2]
        update(1, 0, n - 1, y_to_index[y1], y_to_index[y2], typ)
        prev_x = x  # 更新 prev_x 为当前 x

    return area


import bisect


def paint_area_deepseek(arr):
    """deepseek给出的答案"""
    # 处理输入, 标准化每个矩形的坐标
    normalized = []
    events = []
    y_values = set()

    for rect in arr:
        x1, y1, x2, y2 = rect
        # 确保x1 <= x2, y1 <= y2
        x1, x2 = sorted([x1, x2])
        y1, y2 = sorted([y1, y2])
        normalized.append((x1, y1, x2, y2))
        # 收集所有y坐标用于离散化
        y_values.add(y1)
        y_values.add(y2)
        # 添加事件点
        events.append((x1, 'start', y1, y2))
        events.append((x2, 'end', y1, y2))

    if not y_values:
        return 0

    # 离散化y坐标
    sorted_y = sorted(y_values)
    n = len(sorted_y)
    if n < 2:
        return 0  # 无法形成面积

    # 定义线段树
    class SegmentTree:
        def __init__(self, boundaries):
            self.boundaries = boundaries
            self.size = len(boundaries) - 1
            self.cover = [0] * (4 * self.size)
            self.length = [0] * (4 * self.size)

        def update(self, y1, y2, val):
            # 找到y1和y2对应的区间索引
            left = bisect.bisect_left(self.boundaries, y1)
            right = bisect.bisect_left(self.boundaries, y2)
            if left < right:
                self._update(1, 0, self.size, left, right, val)

        def _update(self, node, l, r, ul, ur, val):
            if ul >= r or ur <= l:
                return
            if ul <= l and r <= ur:
                self.cover[node] += val
            else:
                mid = (l + r) // 2
                self._update(2 * node, l, mid, ul, ur, val)
                self._update(2 * node + 1, mid, r, ul, ur, val)
            # 更新当前区间长度
            if self.cover[node] > 0:
                self.length[node] = self.boundaries[r] - self.boundaries[l]
            else:
                if r - l == 1:
                    self.length[node] = 0
                else:
                    self.length[node] = self.length[2 * node] + self.length[2 * node + 1]

        def query(self):
            return self.length[1]

    st = SegmentTree(sorted_y)
    events.sort(key=lambda x: (x[0], -1 if x[1] == 'start' else 1))

    total_area = 0
    prev_x = None

    for event in events:
        x, typ, y1, y2 = event
        if prev_x is not None and x != prev_x:
            dx = x - prev_x
            total_area += dx * st.query()
        st.update(y1, y2, 1 if typ == 'start' else -1)
        prev_x = x

    return total_area


if __name__ == '__main__':
    # n = int(input())
    # inp = []
    # for i in range(n):
    #     inp.append(map(int, input().split()))

    # 图例中的输入:
    inp = [[1, 7, 10, 11],
           [5, 1, 22, 5],
           [8, 3, 17, 9]]
    print(paint_area(inp))
    print(paint_area_deepseek(inp))

    inp = [[1, 5, 10, 10],
           [3, 1, 20, 20],
           [2, 7, 15, 17]]
    print(paint_area(inp))
    print(paint_area_deepseek(inp))
